package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

import java.util.Arrays;
import java.util.Locale;

/**
 * 重建二叉树
 *
 * @author yuhushuan
 * @date 2020/6/1 00:07
 */
public class _07_1_ConstructBinaryTree {

    public static void main(String[] args) {

        int[] preOrder, inOrder;
        preOrder = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
        inOrder = new int[]{4, 7, 2, 1, 5, 3, 8, 6};

        print(preOrder, inOrder, preOrder.length);
    }

    private static void print(int[] preOrder, int[] inOrder, int length) {
        System.out.println(String.format(Locale.getDefault(),
                "前序遍历：%s\n中序遍历：%s",
                Arrays.toString(preOrder), Arrays.toString(inOrder)));
        System.out.println("重建二叉树");
        BinaryTreeNode head = construct(preOrder, inOrder, length);

        System.out.println("二叉树的前序遍历：");
        BinaryTreeNode.preOrderTraversal_Recursively(head);
        System.out.println();

        System.out.println("二叉树的中序遍历：");
        BinaryTreeNode.inOrderTraversal_Recursively(head);
        System.out.println();
    }

    /**
     * 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如，输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6}，
     * 则重建如图所示的二叉树并输出它的头结点。
     *
     * @param preOrder
     * @param inOrder
     * @param length
     * @return
     */
    private static BinaryTreeNode construct(int[] preOrder, int[] inOrder, int length) {
        if (preOrder == null || inOrder == null || length <= 0) {
            return null;
        }
        return constructCore(preOrder, 0, length - 1, inOrder, 0, length - 1);
    }

    private static BinaryTreeNode constructCore(int[] preOrder, int startPre, int endPre,
                                                int[] inOrder, int startIn, int endIn) {
        // 前序遍历的第一个数字是跟节点的值
        int rootValue = preOrder[startPre];
        BinaryTreeNode root = new BinaryTreeNode();
        root.value = rootValue;
        root.left = root.right = null;

        if (startPre == endPre) {
            return root;
        } else {
            // 在中序遍历中找到根节点的索引
            int rootIn = startIn;
            for (; rootIn <= endIn; rootIn++) {
                if (inOrder[rootIn] == rootValue) {
                    break;
                }
            }
            if (rootIn == endIn && inOrder[rootIn] != rootValue) {
                throw new IllegalArgumentException("两种遍历数据不一致，无法构建二叉树");
            }
            // 左子树中序遍历
            int leftLength = rootIn - startIn;
            if (leftLength > 0) {// 构建左子树
                root.left = constructCore(preOrder, startPre + 1, startPre + leftLength,
                        inOrder, startIn, rootIn - 1);
            }
            if (endIn - startIn - leftLength > 0) {// 构建右子树
                root.right = constructCore(preOrder, startPre + 1 + leftLength, endPre,
                        inOrder, rootIn + 1, endIn);
            }
        }
        return root;
    }
}
